//
// Created by 麻再挺 on 2022/1/12.
//

#include "merge_sort.h"

/**
 * 把两个数组合并起来并保存在第一个列表
 * @param t1 列表 1
 * @param l1 长度 1
 * @param t2 列表 2
 * @param l2 长度 2
 */
void merge(int *t1, int l1, int *t2, int l2) {
    // 临时数组
    int temp[l1 + l2];
    // 变量
    int i, j, k;
    i = j = k = 0;
    // 遍历赋值
    while (i < l1 && j < l2) {
        if (t1[i] < t2[j]) {
            temp[k++] = t1[i++];
        } else {
            temp[k++] = t2[j++];
        }
    }
    while (i < l1) {
        temp[k++] = t1[i++];
    }
    while (j < l2) {
        temp[k++] = t2[j++];
    }
    // 依次赋值
    for (int m = 0; m < l1 + l2; ++m) {
        t1[m] = temp[m];
    }
}

void merge_sort(int a[], int len) {
    if (len > 1) {
        // 取中间值
        int l1 = len / 2;
        int *t1 = a;
        int *t2 = a + l1;
        int l2 = len - l1;
        // 左边
        merge_sort(t1, l1);
        // 右边
        merge_sort(t2, l2);
        // 把两个合在一起
        merge(t1, l1, t2, l2);
    }
}
